Description
墨墨突然对等式很感兴趣,他正在研究a1x1+a2y2+…+anxn=B存在非负整数解的条件,他要求你编写一个程序,给定N、{an}、以及B的取值范围,求出有多少B可以使等式存在非负整数解。
输入的第一行包含3个正整数,分别表示N、BMin、BMax分别表示数列的长度、B的下界、B的上界。输入的第二行包含N个整数,即数列{an}的值。
Output
输出一个整数,表示有多少b可以使等式存在非负整数解。
2 5 10
3 5
Sample Output
5
HINT
对于100%的数据,N≤12,0≤ai≤5*10^5,1≤BMin≤BMax≤10^12。
Solution
本来是想练练dijkstra,然后翻到了这个神题,太神了~
首先第一反应 应该是背包dp,但是数据范围就无语了。。。
也没有什么好引入的把,,,就是一个思维题。。。
记
假设 p 是符合条件的B值,那么显然 p+mn 也是符合条件的
而任意一个p 都可以被表示成:
其中
而每个 p 和一个 r 唯一对应,所以我们只需要知道那些p值是可以用ai表示出来的就好,而我们只需要求那个最小的。
如果记 ans[m]为[1,m]内的答案,那么显然这满足前缀和的性质。
若
且 Vx 是其对应的一个有效最小值,那么其对答案的贡献就是
然后求和就可以了2333333
然后至于为什么dijktra可以判断出一个有效值,先说一下连边方式:
按照这样子连边是不会连出不合法的解,因为权值都是ai。
最短路是保证了解最小的性质。
以上.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56
| #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <iostream> #include <queue> #define pa pair<int,int> #define LL long long using namespace std; const int INF=2147483647; int n,mn=INF,p[5000010],cnt; LL L,R,ans=0,dis[5000010]; int a[20]; bool vis[5000010]; struct node{ int a,b,nt,w; }e[6000010]; void add(int x,int y,int z){ e[++cnt].a=x,e[cnt].b=y,e[cnt].w=z; e[cnt].nt=p[x],p[x]=cnt; } priority_queue<pa,vector<pa>,greater<pa> >q; void dijkstra(){ memset(dis,127,sizeof(dis)); q.push(make_pair(0,0)); dis[0]=0; while(!q.empty()){ int now=q.top().second;q.pop(); if(vis[now])continue;vis[now]=true; for(int i=p[now];i;i=e[i].nt){ int to=e[i].b; if(dis[to]>dis[now]+e[i].w){ dis[to]=dis[now]+e[i].w; q.push(make_pair(dis[to],to)); } } } } int main(){ #ifdef YSW freopen("in.txt","r",stdin); #endif scanf("%d%lld%lld",&n,&L,&R); for(int i=1;i<=n;i++)scanf("%d",&a[i]),mn=min(mn,a[i]); for(int i=0;i<mn;i++) for(int j=1;j<=n;j++){ add(i,(i+a[j])%mn,a[j]); } dijkstra(); for(int i=0;i<mn;i++){ if(R>=dis[i])ans+=(R-dis[i])/mn+1; if(L-1>=dis[i])ans-=(L-1-dis[i])/mn+1; } printf("%lld",ans); return 0; }
|